package algorithm.sort;

import org.junit.Before;
import org.junit.Test;

import java.util.Arrays;

/**
 * 选择排序
 * 　　简单选择排序是最简单直观的一种算法，基本思想为每一趟从待排序的数据元素中选择最小（或最大）的一个元素作为首元素，
 * 直到所有元素排完为止，简单选择排序是不稳定排序。
 * 　　在算法实现时，每一趟确定最小元素的时候会通过不断地比较交换来使得首位置为当前最小，交换是个比较耗时的操作。
 * 其实我们很容易发现，在还未完全确定当前最小元素之前，这些交换都是无意义的。我们可以通过设置一个变量min，每一次比较仅存储较小元素的数组下标，
 * 当轮循环结束之后，那这个变量存储的就是当前最小元素的下标，此时再执行交换操作即可。
 */
public class SelectSort {

    private final int[] arr = new int[15];

    @Before
    public void init() {
        for (int i = 0, j = arr.length; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * j);
        }
    }

    @Test
    public void sort() {
        System.out.println("排序前:" + Arrays.toString(arr));
        for (int i = 0, len = arr.length; i < len; i++) {
            //每一趟循环比较时，min用于存放较小元素的数组下标，这样当前批次比较完毕最终存放的就是此趟内最小的元素的下标，避免每次遇到较小元素都要进行交换。
            int min = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[min]) {
                    min = j;
                }
            }
            //进行交换，如果min发生变化，则进行交换
            if (min != i) {
                arr[i] = arr[i] ^ arr[min];
                arr[min] = arr[i] ^ arr[min];
                arr[i] = arr[i] ^ arr[min];
            }
        }
        System.out.println("排序后:" + Arrays.toString(arr));
    }
}
